import random

class Subarray:
    def __init__(self):
        self.start = 0  # inclusive
        self.end = 0    # exclusive
        self.val = 0

def highest_value_subarray(arr):
    best = Subarray()
    bestWithK = Subarray()
    
    if len(arr) == 0:
        return best

    # init base case
    if arr[0] > 0:
        best.end = 1
        best.val = arr[0]
    
    bestWithK.end = 1
    bestWithK.val = arr[0]

    # after each iteration, best will contain the highest-value
    # subarray using elements from 0 to k inclusive, and bestWithK
    # will contain the highest-vlue subbarray that contains the kth
    # element and uses elements from 0 to k inclusive.
    for k in range(1, len(arr)):
        bestWithK.end = k + 1
        if bestWithK.val > 0:
            bestWithK.val += arr[k]
        else:
            bestWithK.start = k
            bestWithK.val = arr[k]
        if bestWithK.val > best.val:
            best.start = bestWithK.start
            best.end = bestWithK.end
            best.val = bestWithK.val

    return best

if __name__ == "__main__":

    l = random.sample(set(range(-100,100)), 20)
    print(l)
    print("highest-value subarray:")
    best = highest_value_subarray(l)
    print(l[best.start : best.end])
    print("value:")
    print(str(best.val))
    